#include "thread.h"
#include "coneSampling.h"
#include <iostream>
#include <queue>
#include <stack>
#include <time.h>

bool Cone :: number_dffs(CircuitGraph& GraphIn){
        
        cout<<"Numbering DFFs Begins......."<<endl;
        
        //add ids to the DFFs
        int i, dff_cnt = 0;
        int vn = boost::num_vertices(GraphIn) ;
        
        for( i = 0; i < vn; i++)
        {
                if(GraphIn[i].gateType == 2 )
                        GraphIn[i].dff_id = dff_cnt++;
                else
                        GraphIn[i].dff_id = -1;
        }
        
        return true;
}


bool Cone :: topo_order_whole_graph(CircuitGraph& GraphIn)
{

        cout<<"Topological Ordering of the Whole Graph Begins......."<<endl;
        
        //if the verteces are given in the order from PI to PO, this topo
        //order is a good approximation
        //break the loops by neglect the loop back edges
        int topo_id = 0, flag;
        int incomming_vertices;
        int vn = boost::num_vertices(GraphIn) ;
        
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;
                
        //cout<<"nember of verteces is "<< vn <<endl;
        while(topo_id < vn)
        {
                //cout<<"Inside!"<<endl;                                                                                                                                    
                for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                {
                        //cout<<"Here Here !"<<endl;                                                                                            
                        //cout<<"Node is "<< GraphIn[(*vi)].instanceName <<
                        //"\t" << GraphIn[(*vi)].cellName <<endl;                                                                                  
                        
                        //cout<<"Value is "<< GraphIn[(*vi)].visited
                        //<<endl;                                                                                                                         
                        if(GraphIn[(*vi)].visited == 0) 
                        {
                                flag = 0;
                                incomming_vertices = boost::in_degree(*vi, GraphIn);
                                //cout<<"Degree is "<< incomming_vertices
                                //<< endl;                                                                                                                   

                                if(incomming_vertices == 0){
                                        GraphIn[(*vi)].visited = 1;
                                        GraphIn[(*vi)].topo_id = topo_id++; 
                                }
                                else
                                {
                                        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices((*vi), GraphIn) ; 
                                             in_vi != in_vi_end ; ++in_vi)
                                        {
                                                
                                                //cout<<"Fanin Node is "<<
                                                //GraphIn[(*in_vi)].instanceName
                                                //<< "\t" <<
                                                //GraphIn[(*in_vi)].cellName
                                                //<<endl;                                              
                                                if(GraphIn[(*in_vi)].visited == 1 || GraphIn[(*in_vi)].gateType == 3)
                                                        continue;
                                                else
                                                {
                                                        flag = 1;
                                                        break;
                                                }
                                        }
                                        
                                        if(flag == 0){
                                                GraphIn[(*vi)].visited = 1;
                                                GraphIn[(*vi)].topo_id = topo_id++; 
                                        }
                                }
                        }
                }
        }
}


CircuitGraph* GraphInPtr;
bool topo_sort(vertex_descriptor i1, vertex_descriptor i2)
{
        return ((*GraphInPtr)[i1].topo_id < (*GraphInPtr)[i2].topo_id);
}


bool Cone :: topo_order_dffs(CircuitGraph& GraphIn)
{
        
        vertex_descriptor node;
        std::queue<vertex_descriptor> worklist;
        CircuitGraph::adjacency_iterator in_vi, in_vi_end ;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                if(GraphIn[(*vi)].gateType == 0)
                        worklist.push(*vi);
        
        while(!worklist.empty())
        {
                node = worklist.front();
                
                if(GraphIn[node].visited == 1)
                {
                        worklist.pop();
                        continue;
                }
                
                GraphIn[node].visited = 1;
                if(GraphIn[node].gateType == 3)
                {
                        this->worklist.push_back(node);
                }
                
                for (boost::tie(in_vi, in_vi_end) = boost::adjacent_vertices(node, GraphIn) ; in_vi != in_vi_end ; ++in_vi)
                        worklist.push(*in_vi);
                
                worklist.pop();
        }

        std::vector<vertex_descriptor>::iterator it;
        //cout<<"Sequential size is "<<this->worklist.size()<<endl;
        //for(it = this->worklist.begin(); it != this->worklist.end(); it++)
        //cout<<*it<<"\t";
        //cout<<endl;

        return true;
}


bool Cone :: form_cones(CircuitGraph& GraphIn)
{
        cout<<"Forming Cones Begins......."<<endl;
        
        int total_comb_node_num = 0;
        std::queue<vertex_descriptor> covered_nodes;
        std::vector<vertex_descriptor> coveredNodes;
        std::vector<vertex_descriptor>::iterator it;
        std::vector<vertex_descriptor>::iterator it2;
        
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;
        for(it = this->worklist.begin(); it != this->worklist.end(); it++)
        {
                
                cone mycone;
                coveredNodes.clear();
                covered_nodes.push(*it);
                
                while(!covered_nodes.empty())
                {
                        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(covered_nodes.front(), GraphIn); 
                             in_vi != in_vi_end ; ++in_vi)
                        {
                                if(GraphIn[(*in_vi)].gateType == 2 && GraphIn[(*in_vi)].visited == 0)
                                {
                                        //GraphIn[(*in_vi)].visited = 1;
                                        coveredNodes.push_back(*in_vi);
                                        covered_nodes.push(*in_vi);
                                }
                        }
                        
                        covered_nodes.pop();
                }
                
                mycone.done = 0;
                mycone.gate_idx = *it;
                total_comb_node_num += coveredNodes.size();
                //cout<<"nodes num in a cone is " << coveredNodes.size()<<endl;
                std::swap(mycone.gate_ids, coveredNodes);
                this->cones.push_back(mycone);
        }
        
        //cout<<"total Sequential nodes number is "<<this->worklist.size() <<endl;
        //cout<<"total Combinational nodes number is "<<total_comb_node_num <<endl;
        return true;
}


bool Cone :: extract_critical_path(vertex_descriptor &vi, const int cone_id, CircuitGraph& GraphIn)
{
        int flag = 0;
        double temp_violation = 0.0;
        vertex_descriptor cur_candidate;

        //if(GraphIn[vi].gateType == 3)
        //cout<<"DFF name "<< GraphIn[vi].instanceName<<" has fan in nodes:"<<endl;
                        
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end;
        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(vi, GraphIn); 
             in_vi != in_vi_end ; ++in_vi)
        {
                //if(GraphIn[vi].gateType == 3)
                //cout<<GraphIn[*in_vi].instanceName << "\t" << GraphIn[*in_vi].cellName << "\t"
                //<< GraphIn[*in_vi].Slack_Violation + GraphIn[*in_vi].Slew_Violation << endl;

                //cout<<"current node is "<< *in_vi <<endl;
                if( std::find(this->cones[cone_id].gate_ids.begin(),
                              this->cones[cone_id].gate_ids.end(),*in_vi) == this->cones[cone_id].gate_ids.end() )
                        continue;
                
                //backtrack, choosing nodes based on the timing violation
                if(temp_violation <= GraphIn[(*in_vi)].Slew_Violation + GraphIn[(*in_vi)].Slack_Violation)
                        //if(temp_violation <= GraphIn[(*in_vi)].Slew_Violation + GraphIn[(*in_vi)].Slack_Violation + GraphIn[(*in_vi)].Cap_Violation)
                {
                        flag = 1;
                        cur_candidate = *in_vi;
                        //temp_violation = GraphIn[(*in_vi)].Slew_Violation + GraphIn[(*in_vi)].Slack_Violation + GraphIn[(*in_vi)].Cap_Violation;
                        temp_violation = GraphIn[(*in_vi)].Slew_Violation + GraphIn[(*in_vi)].Slack_Violation;
                }
        }
        
        if(flag == 1)
        {
                //cout<<"node id is "<<cur_candidate <<" timing violation is "<< temp_violation <<endl;
                this->cones[cone_id].critical_path.push_back(cur_candidate);
                vi = cur_candidate;
        }
        else
                return true;
        
        return false;
}


bool same_vertex(vertex_descriptor v1, vertex_descriptor v2)
{
        return (v1 == v2);
}


bool Cone :: form_hybrid_cones(CircuitGraph& GraphIn)
{
        int cone_id, i ,j;
        std::vector<vertex_descriptor> temp;
        std::vector<int>::iterator it;
        std::vector<vertex_descriptor>::iterator it_vi, it_vi2;
        
        //this is important
        this->big_cones.clear();
        
        int path_length = 0; int count_real_cone = 0;
        for(cone_id = 0; cone_id < this->cones.size(); cone_id++)
        {
                if(this->cones[cone_id].done == 1)
                        continue;
                
                if(this->cones[cone_id].gate_ids.size() == 0)
                        continue;
                
                this->cones[cone_id].critical_path.clear();
                this->cones[cone_id].critical_path.push_back(this->cones[cone_id].gate_idx);
                //cout<<"In normal cone "<<cone_id<<endl;
                //cout<<"total timing violation "<< this->cones[cone_id].total_timing_viol<<endl;
                vertex_descriptor v = this->cones[cone_id].gate_idx;
                while(this->extract_critical_path(v, cone_id, GraphIn) == false);
                
                //remove DFF
                this->cones[cone_id].critical_path.erase(this->cones[cone_id].critical_path.begin());
                
                count_real_cone++;
                path_length += this->cones[cone_id].critical_path.size();
                //cout<<"Critical path has gates: "<<endl;
                //for(it_vi = this->cones[cone_id].critical_path.begin(); it_vi != this->cones[cone_id].critical_path.end(); it_vi++)
                //cout<<*it_vi<<"\t"<<GraphIn[*it_vi].Slack_Violation + GraphIn[*it_vi].Slew_Violation<<endl;
        }
        
        cout<<"Average length of the path is "<< (double)path_length / (double) count_real_cone<<endl;; 
        //let's assume now only two can form a large cone
        for(i = 0; i < this->cones.size(); i++)
        {
                if(this->cones[i].done == 1)
                        continue;
                
                for(j = i + 1; j < this->cones.size(); j++)
                {
                        if(this->cones[j].done == 1)
                                continue;
                        
                        temp.clear();
                        
                        for(it_vi = this->cones[i].critical_path.begin(); it_vi != this->cones[i].critical_path.end(); it_vi++)
                        {
                                for(it_vi2 = this->cones[j].critical_path.begin(); it_vi2 != this->cones[j].critical_path.end(); it_vi2++)
                                        if(*it_vi == *it_vi2)
                                                temp.push_back(*it_vi);
                        }
                        
                        if(!temp.empty())
                        {
                                big_cone MyBC;
                                MyBC.done = 0;
                                MyBC.merged = 0;
                                std::swap(MyBC.common_gates, temp);
                                MyBC.cone_ids.push_back(i);
                                MyBC.cone_ids.push_back(j);
                                this->cones[i].done = 1;
                                this->cones[j].done = 1;
                                this->big_cones.push_back(MyBC);
                                break;
                        } 
                        
                }
        }

        //here, for some of the cones that pass the timing check, we do not
        //consider them in forming the big cones
        for(i = 0; i < this->cones.size(); i++)
        {
                if(this->cones[i].done == 0)//single
                {
                        big_cone MyBC;
                        MyBC.done = 0;
                        MyBC.merged = 0;
                        MyBC.common_gates = this->cones[i].critical_path;
                        MyBC.cone_ids.push_back(i);
                        this->cones[i].done = 1;
                        this->big_cones.push_back(MyBC);
                }
        }
        
        /*
        int count = 0;
        for(i = 0; i < this->big_cones.size(); i++)       
        {
                count += this->big_cones[i].cone_ids.size();
        }
        cout<<"First Round...."<<endl;
        cout<<"big cone num is "<< this->big_cones.size() << endl;
        cout<<"sequential gate counnt is "<< count << endl;
        */

        //one more step for more intersection, result in big cone of at
        //most 4 normal cones
        for(i = 0; i < this->big_cones.size(); i++)
        {
                if(this->big_cones[i].done == 1)
                        continue;
                                
                for(j = i + 1; j < this->big_cones.size(); j++)
                {
                        if(this->big_cones[j].done == 1)
                                continue;
                        
                        temp.clear();
                        
                        for(it_vi = this->big_cones[i].common_gates.begin(); it_vi != this->big_cones[i].common_gates.end(); it_vi++)
                        {
                                for(it_vi2 = this->big_cones[j].common_gates.begin(); it_vi2 != this->big_cones[j].common_gates.end(); it_vi2++)
                                        if(*it_vi == *it_vi2)
                                                temp.push_back(*it_vi);
                        }
                        
                        if(!temp.empty())
                        {
                                big_cone MyBC;
                                MyBC.done = 1;
                                MyBC.merged = 0;
                                std::swap(MyBC.common_gates, temp);
                                
                                for(it = this->big_cones[i].cone_ids.begin(); it != this->big_cones[i].cone_ids.end(); it++)
                                        MyBC.cone_ids.push_back(*it);
                                
                                for(it = this->big_cones[j].cone_ids.begin(); it != this->big_cones[j].cone_ids.end(); it++)
                                        MyBC.cone_ids.push_back(*it);
                                
                                this->big_cones[i].done = 1;
                                this->big_cones[i].merged = 1;
                                this->big_cones[j].done = 1;
                                this->big_cones[j].merged = 1;
                                this->big_cones.push_back(MyBC);
                                break;
                        }
                }
        }
        
        //count = 0;
        for(i = 0; i < this->big_cones.size(); )
        {
                if(this->big_cones[i].merged == 1)
                {
                        this->big_cones.erase(this->big_cones.begin() + i);
                        continue;
                }
                
                this->big_cones[i].done = 0;
                this->big_cones[i].total_timing_viol = 0.0;
                
                for(it = this->big_cones[i].cone_ids.begin(); it != this->big_cones[i].cone_ids.end(); it++)
                        this->big_cones[i].total_timing_viol += this->cones[*it].total_timing_viol;
                
                //count += this->big_cones[i].cone_ids.size();
                i++;
        }
        
        //cout<<"Second Round...."<<endl;
        //cout<<"big cone num is "<< this->big_cones.size() << endl;
        //cout<<"sequential gate counnt is "<< count << endl;
        
        /*
        for(i = 0; i < this->big_cones.size(); i++)
        {
                cout<<"Big Cone id "<< i << " has common gates: " << endl;
                for(it_vi = this->big_cones[i].common_gates.begin(); it_vi != this->big_cones[i].common_gates.end(); it_vi++)
                        cout<<*it_vi<<"\t";
                cout<<endl;
                
                for(it = this->big_cones[i].cone_ids.begin(); it != this->big_cones[i].cone_ids.end(); it++)
                {
                        cout<<"normal cone id "<< *it << " has critical path:" <<endl;
                        for(it_vi = this->cones[*it].critical_path.begin(); it_vi != this->cones[*it].critical_path.end(); it_vi++)
                                cout<<*it_vi<<"\t";
                        cout<<endl;
                }
        }
        */
        
        this->reset_cones();
        return true;
}


bool Cone :: clear_flag(CircuitGraph& GraphIn)
{
        int i;
        int vn = boost::num_vertices(GraphIn) ;
        
        for( i = 0; i < vn; i++)
        {
                GraphIn[ i ].fixed = 0;
                GraphIn[ i ].touched = 0;
                GraphIn[ i ].visited = 0;
        }
}


bool Cone :: reset_cones()
{
        for(int i = 0; i < this->cones.size(); i++)
                this->cones[i].done = 0;
        
        return true;
}


int Cone :: find_samples_per_gate(CircuitGraph& GraphIn, vertex_descriptor& vi, const int big_cone_id, const int NSamples, const bool critical, const int coarse)
{
        bool state;
        int sample_size, start_size_num = 3;
        
        //sample_size = GraphIn[vi].noCapViolationCells.size();
        double temp = (GraphIn[vi].Slack_Violation + GraphIn[vi].Slew_Violation) / this->big_cones[big_cone_id].most_violation;
        sample_size = (temp < 0.2)? 0 : (temp < 0.5 && temp > 0.2)? 2 : (temp < 0.8 && temp > 0.5)? 3 : 4;
        
        if(!critical)
        {
                //if(sample_size >= 4)
                //sample_size = 4;
                
                GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 1, state);
                //if(state == false)
        }
        else
        {
                //if(sample_size >= start_size_num + coarse)
                //sample_size = start_size_num + coarse;
                sample_size = 3;
                GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 0.5, state);
                //if(state == false)
        }
        
        if(GraphIn[vi].ReducedCellSet.size() == 0)
        {
                GraphIn[vi].ReducedCellSet.clear();
                string str = GraphIn[vi].footPrint + "s01"; 
                GraphIn[vi].ReducedCellSet.push_back(str);
                
                return 1;
        }
        
        // //coarse only applies to the critical gates
        // if(coarse && critical)
        // {
        //         sample_size = 4;
        //         GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 0.5, state);
                
        //         //GraphIn[vi].ReducedCellSet.clear();
        //         //min leakage
        //         //string str = GraphIn[vi].footPrint + "s01"; 
        //         //GraphIn[vi].ReducedCellSet.push_back(str);
        //         //min delay
        //         //str = GraphIn[vi].footPrint + "m80"; 
        //         //GraphIn[vi].ReducedCellSet.push_back(str);
        // }
        // else
        // {
        //         sample_size = (GraphIn[vi].noCapViolationCells.size() >= NSamples)? NSamples : GraphIn[vi].noCapViolationCells.size();
                
        //         if(!critical)
        //         {
                        
        //                 //double temp = (GraphIn[vi].Slack_Violation + GraphIn[vi].Slew_Violation) / this->big_cones[big_cone_id].most_violation;
        //                 //sample_size = (temp < 0.2)? 0 : (temp < 0.5 && temp > 0.2)? GraphIn[vi].noCapViolationCells.size() * 0.3 
        //                 //: (temp < 0.8 && temp > 0.5)? GraphIn[vi].noCapViolationCells.size() * 0.7 : GraphIn[vi].noCapViolationCells.size(); 
        //                 sample_size = 4;
        //                 if(sample_size > 0)
        //                 {
        //                         GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 1, state);
        //                 }
        //                 else
        //                 {
        //                         GraphIn[vi].ReducedCellSet.clear();
        //                         string str = GraphIn[vi].footPrint + "s01"; 
        //                         GraphIn[vi].ReducedCellSet.push_back(str);
        //                 }
        //         }
        //         else
        //         {
        //                 //if(GraphIn[vi].noCapViolationCells.size() > 6)
        //                 sample_size = 2;
                        
        //                 GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 0.5, state);
        //         }
        // }
        
        // //if(GraphIn[vi].ReducedCellSet.size() == 0)
        // //cout<<"no way!"<<endl;
        
        return GraphIn[vi].ReducedCellSet.size();
}


int Cone :: find_samples_per_gate2(CircuitGraph& GraphIn, vertex_descriptor& vi, const double root_violation, const bool critical)
{
        bool state;
        int sample_size, start_size_num = 3;
        
        double temp = (GraphIn[vi].Slack_Violation + GraphIn[vi].Slew_Violation) / root_violation;
        sample_size = (temp < 0.2)? 0 : (temp < 0.5 && temp > 0.2)? 2 : (temp < 0.8 && temp > 0.5)? 3 : 4;
        
        if(!critical)
        {
                //GraphIn.SampleGateNearby(vi, GraphIn[vi].cellName, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0.3, 0.5, state);
                GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0.5, 1, state);
        }
        else
        {
                sample_size = 5;
                //GraphIn.SampleGateNearby(vi, GraphIn[vi].cellName, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0.1, 0.3, state);
                GraphIn.stepSampleGateAngle(vi, *(this->LpPtr), sample_size, GraphIn[vi].ReducedCellSet, 0, 0.5, state);
        }
        
        if(GraphIn[vi].ReducedCellSet.size() == 0)
        {
                GraphIn[vi].ReducedCellSet.clear();
                string str = GraphIn[vi].footPrint + "s01"; 
                GraphIn[vi].ReducedCellSet.push_back(str);
                
                return 1;
        }
        
        assert(GraphIn[vi].ReducedCellSet.size() < 10);
        return GraphIn[vi].ReducedCellSet.size();
}


bool DFS_path_blossum(stack<vertex_descriptor>& activeGates, pathBlossum& PB, CircuitGraph& GraphIn)
{
        int flag = 0;
        double node_vio;
        
        vertex_descriptor vi = activeGates.top();
        //cout<<"Top "<< vi <<endl;
        CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
        
        for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(vi, GraphIn); 
             adj_vi != adj_vi_end ; ++adj_vi)
        {
                if(GraphIn[*adj_vi].gateType != 2 || GraphIn[*adj_vi].touched == 1)
                        continue;
                
                //node_vio = GraphIn[*adj_vi].Slack_Violation +
                //GraphIn[*adj_vi].Slew_Violation + GraphIn[*adj_vi].Cap_Violation;
                node_vio = GraphIn[*adj_vi].Slack_Violation + GraphIn[*adj_vi].Slew_Violation;
                if(node_vio <= 0.8 * PB.root_violation)
                        continue;
                
                flag = 1;
                //cout<<"here node "<<*adj_vi<<endl;
                activeGates.push(*adj_vi);
                break;
        }
        
        if(flag == 0)
        {
                //cout<<"pre "<< vi <<endl;
                //cout<<"cur "<< activeGates.top() <<endl;
                //cout<<"touched? "<< GraphIn[activeGates.top()].touched <<endl;
                if(GraphIn[activeGates.top()].touched == 0)
                {
                        vector<vertex_descriptor> onePath;
                        stack<vertex_descriptor> temp(activeGates);
                        //cout<<"size is "<<activeGates.size()<<endl;
                        while(!temp.empty())
                        {
                                onePath.push_back(temp.top());
                                temp.pop();
                        }
                        
                        PB.critical_paths.push_back(onePath);
                        GraphIn[activeGates.top()].touched = 1;
                }
                
                activeGates.pop();
                if(activeGates.empty())        
                        return true;
                else
                        DFS_path_blossum(activeGates, PB, GraphIn);
                
        }
        else
        {
                GraphIn[vi].touched = 1;
                DFS_path_blossum(activeGates, PB, GraphIn);
        }
}

bool find_fanout_critical_path(vertex_descriptor &vi, CircuitGraph& GraphIn)
{
        int flag = 0;
        double temp_violation = 0.0;
        vertex_descriptor cur_candidate;
        
        CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
        for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(vi, GraphIn); 
             adj_vi != adj_vi_end ; ++adj_vi)
        {
                //backtrack, choosing nodes based on the timing violation
                if(temp_violation <= GraphIn[(*adj_vi)].Slew_Violation + GraphIn[(*adj_vi)].Slack_Violation)
                {
                        flag = 1;
                        cur_candidate = *adj_vi;
                        temp_violation = GraphIn[(*adj_vi)].Slew_Violation + GraphIn[(*adj_vi)].Slack_Violation;
                }
        }
        
        if(flag == 1)
        {               
                //cout<<"node id is "<<cur_candidate <<" timing violation is "<< temp_violation <<endl;
                vi = cur_candidate;
                
                if(GraphIn[cur_candidate].gateType != 2)
                        return true;
        }
        
        return false;
}


bool DFS(vertex_descriptor &vi, set<vertex_descriptor>& temp, stack<vertex_descriptor>& myStack, CircuitGraph& GraphIn)
{
        int flag = 0;
        if(boost::out_degree(vi,GraphIn) == 0)
                return true;
        
        CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
        for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(vi, GraphIn); 
             adj_vi != adj_vi_end ; ++adj_vi)
        {
                if(GraphIn[*adj_vi].gateType != 2)
                        continue;

                if(GraphIn[*adj_vi].fixed == 1)
                        return false;
                else
                {
                        flag = 1;                        
                        temp.insert(*adj_vi);
                        myStack.push(*adj_vi);
                        break;
                }
        }
        
        if(flag == 0)
                return true;
        else
        {
                vi = myStack.top();
                DFS(vi, temp, myStack, GraphIn);
        }
}


void choose_3_consecutive(CircuitGraph& GraphIn, double threshold, vertex_descriptor &in, vector<vertex_descriptor>& critical_gates)
{
        
        double                               temp_totalViol = 0.0;
        vertex_descriptor                    cur_worst;
        CircuitGraph::adjacency_iterator     vi, vi_end ;
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;

        //first is always the root node
        critical_gates.push_back(in);
        
        //fill in the critical gates
        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(in, GraphIn); in_vi != in_vi_end ; ++in_vi)
                if(GraphIn[*in_vi].gateType == 2)
                        critical_gates.push_back(*in_vi);
        
        for (boost::tie(vi, vi_end) = boost::adjacent_vertices(in, GraphIn); vi != vi_end ; ++vi)
                if(GraphIn[*vi].gateType == 2)
                        if(GraphIn[*vi].Slack_Violation + GraphIn[*vi].Slew_Violation + GraphIn[*vi].Cap_Violation > temp_totalViol)
                        {
                                cur_worst = *vi;
                                temp_totalViol = GraphIn[*vi].Slack_Violation + GraphIn[*vi].Slew_Violation + GraphIn[*vi].Cap_Violation;
                        }
        
        if(temp_totalViol > 0.5 * threshold)
                critical_gates.push_back(cur_worst);

}


bool Cone :: critical_gates_per_path(CircuitGraph& GraphIn, vector<vertex_descriptor>& path, vector<vertex_descriptor>& critical_gates)
{
        
        double temp_violation;
        set<vertex_descriptor> temp;
        set<vertex_descriptor>::iterator it_temp;
        vector<vertex_descriptor>::iterator it;
        std::multimap<double, vertex_descriptor> RankMap;//use a map for rank
        std::multimap<double, vertex_descriptor>::iterator it_RM;
        
        for(it = path.begin(); it != path.end(); it++)
        {
                temp_violation = GraphIn[(*it)].Slew_Violation + GraphIn[(*it)].Slack_Violation;
                RankMap.insert(std::pair<double,vertex_descriptor>(temp_violation,*it));
        }
        
        GraphIn.nodeSlackVector.clear();
        for(it_RM = RankMap.begin(); it_RM != RankMap.end(); it_RM++)
        {
                if(GraphIn[it_RM->second].visited == 1)
                        continue;
                
                if(GraphIn[it_RM->second].gateType != 2)
                        continue;
                
                GraphIn[it_RM->second].level = 0;
                while(find_fanout_critical_path(it_RM->second, GraphIn) == false)
                        GraphIn[it_RM->second].level++;
                GraphIn[it_RM->second].level++;//make sure leveling is not 0
                
                //cout<<"level is "<<GraphIn[*vi].level<<endl;
                double temp_total = 0.0;
                //double temp_total = GraphIn[*vi].Slack_Violation;
                CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
                for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(it_RM->second, GraphIn); 
                     adj_vi != adj_vi_end ; ++adj_vi)
                        temp_total += GraphIn[*adj_vi].Slack_Violation;
                
                GraphIn[it_RM->second].lessSharing = temp_total 
                        / (boost::out_degree(it_RM->second,GraphIn) * GraphIn[it_RM->second].level);
                
                //GraphIn[it_RM->second].lessSharing = GraphIn[it_RM->second].Slack_Violation 
                // * (boost::out_degree(it_RM->second,GraphIn) / GraphIn[it_RM->second].level);
                
                NodeSlackStruct myNSS;
                myNSS.vertexDescriptor = it_RM->second;
                myNSS.negativeSlack = GraphIn[it_RM->second].lessSharing;
                GraphIn.nodeSlackVector.push_back(myNSS);
        }
        
        std::sort(GraphIn.nodeSlackVector.begin(), GraphIn.nodeSlackVector.end(), sortingFunction());
        
        vector<NodeSlackStruct>::iterator it_NSV;
        stack<vertex_descriptor> myStack;
        
        int flag = 0;
        myStack.push(GraphIn.nodeSlackVector[0].vertexDescriptor);
        GraphIn[GraphIn.nodeSlackVector[0].vertexDescriptor].visited = 1;
        
        while(!myStack.empty())
                if(DFS(myStack.top(), temp, myStack, GraphIn) == true)
                        myStack.pop();
                else
                {
                        flag = 1;
                        break;
                }
        
        if(flag == 1)
        {
                while (!myStack.empty())
                        myStack.pop();
                temp.clear();
                return false;
        }        
        else
        {
                //if(GraphIn[GraphIn.nodeSlackVector[0]].gateType == 2)
                for(it_temp = temp.begin(); it_temp != temp.end(); it_temp++)
                        GraphIn[*it_temp].visited = 1;
                
                temp.clear();
                
                for(int j = 0; j < GraphIn.nodeSlackVector.size(); j++)
                {
                        vertex_descriptor node = GraphIn.nodeSlackVector[j].vertexDescriptor;
                        if(GraphIn[node].gateType == 2)
                                critical_gates.push_back(node);
                        
                        //assert(critical_gates.size() > 0);
                        if(critical_gates.size() == 5)
                                break;
                }

                //choose_3_consecutive(GraphIn, GraphIn.nodeSlackVector[0].negativeSlack, 
                //GraphIn.nodeSlackVector[0].vertexDescriptor, critical_gates);
                
                return true;        
        }
        
        /*
        vector<NodeSlackStruct>::iterator it_NSS;
        if(GraphIn.nodeSlackVector.size() <= 3)
        {
                for(it_NSS = GraphIn.nodeSlackVector.begin(); it_NSS != GraphIn.nodeSlackVector.end(); it_NSS++)
                        critical_gates.push_back(it_NSS->vertexDescriptor);
        }
        else
        {
                int count = 0;
                for(it_NSS = GraphIn.nodeSlackVector.begin(); it_NSS != GraphIn.nodeSlackVector.end(); it_NSS++)
                {
                        if(count == 3)
                                break;
                        
                        critical_gates.push_back(it_NSS->vertexDescriptor);
                        count++;
                }
        }
        */
}


void Cone :: single_gate_fixing(CircuitGraph& GraphIn, vertex_descriptor &in, vector<vertex_descriptor>& critical_gates)
{
        if(critical_gates.size() == 0)
                return;

        int i, flag;
        const int sample_times = 10;
        int cell_combination, temp_cell_combination;
        int temp_gate_size = 0, critical_gate_sample_size = 0;
        
        double fallSlew, riseSlew, temp_totalViol = 0.0, best_totalViol;
        double fallArrival, riseArrival, temp_total_leakage, best_total_leakage;
        double totalCapViol, totalSlewViol, totalSlackViol, cur_best_timing = 1.0e20;
        
        CircuitGraph::adjacency_iterator vi, vi_end ;
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;

        pathBlossum PB;
        PB.root_node = in;
        //PB.root_violation = GraphIn[in].Slack_Violation + GraphIn[in].Slew_Violation + GraphIn[in].Cap_Violation;
        PB.root_violation = GraphIn[in].Slack_Violation + GraphIn[in].Slew_Violation;

        //find the critical path blossum
        stack<vertex_descriptor> activeGates;
        activeGates.push(in);
        cout<<"Node "<<in<<" Now finding paths...."<<endl;
        DFS_path_blossum(activeGates, PB, GraphIn);
        cout<< "# of paths in this cone " << PB.critical_paths.size() << endl;
        
        vertex_descriptor                             cur_worst, temp_vi;
        vector<vertex_descriptor>::iterator           it_critical;
        vector<vertex_descriptor>::iterator           it_gate;
        vector< vector<vertex_descriptor> >::iterator it_paths;
        
        //cout<<"Node "<<in<<" has paths:"<<endl;
        for(it_paths = PB.critical_paths.begin(); it_paths != PB.critical_paths.end(); it_paths++)
        {
                std::reverse((*it_paths).begin(), (*it_paths).end());
                //for(it_gate = (*it_paths).begin(); it_gate != (*it_paths).end(); it_gate++)
                //cout<<*it_gate<<"\t";
                //cout<<endl;
                //cin.get();
        }
        
        cout<<"critical gates are "<<endl;
        //find samples
        for(it_critical = critical_gates.begin(); it_critical != critical_gates.end(); it_critical++)
        {
                cout<<*it_critical<<"\t";
                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_critical, GraphIn); vi != vi_end ; ++vi)
                {
                        temp_vi = *vi;
                        if(GraphIn[temp_vi].gateType == 2)
                                this->find_samples_per_gate2(GraphIn, temp_vi, PB.root_violation, false);
                }
                
                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_critical, GraphIn); in_vi != in_vi_end ; ++in_vi)
                {
                        temp_vi = *in_vi;
                        if(GraphIn[temp_vi].gateType == 2)
                                this->find_samples_per_gate2(GraphIn, temp_vi, PB.root_violation, false);
                }
                
                if(GraphIn[*it_critical].gateType == 2)
                {
                        GraphIn[*it_critical].visited = 1;
                        temp_gate_size = this->find_samples_per_gate2(GraphIn, *it_critical, PB.root_violation, true);
                }       
                
                if(temp_gate_size > 100)
                        cout<<"No way"<<endl;
                
                if(temp_gate_size > critical_gate_sample_size)
                        critical_gate_sample_size = temp_gate_size;
                
                assert(critical_gate_sample_size < 100);
        }
        cout<<endl;
        cout<<"Sample size is "<< critical_gate_sample_size << endl;
        //cout<<"I'm HERE!"<<endl;
        //sample procedure starts
        for(cell_combination = 0; cell_combination < pow(critical_gate_sample_size, critical_gates.size()); cell_combination++)
        {
                
                flag = 0;
                node_rank* myNR = new node_rank;
                temp_cell_combination = cell_combination;
                best_totalViol = 100000000.0;
                best_total_leakage = 100000000.0;
                
                for(it_critical = critical_gates.begin(); it_critical != critical_gates.end(); it_critical++)
                {
                        if(GraphIn[(*it_critical)].ReducedCellSet.size() != 0)
                        {
                                if(temp_cell_combination % critical_gate_sample_size >= GraphIn[(*it_critical)].ReducedCellSet.size())
                                {
                                        flag = 1;
                                        break;
                                }

                                if(GraphIn[(*it_critical)].gateType == 2 && GraphIn[(*it_critical)].ReducedCellSet.size() != 1)
                                        GraphIn[(*it_critical)].cellName = GraphIn[(*it_critical)].ReducedCellSet[temp_cell_combination % critical_gate_sample_size];
                                
                                temp_cell_combination /= critical_gate_sample_size;
                        }
                }
                
                if(flag == 1)
                        continue;
                
                cout<<"Combinaiton # "<< cell_combination << endl;
                for(i = 0; i < sample_times; i++)
                {
                        srand ( time(NULL) );
                        
                        for(it_critical = critical_gates.begin(); it_critical != critical_gates.end(); it_critical++)
                        {
                                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_critical, GraphIn); vi != vi_end ; ++vi)
                                        if(GraphIn[(*vi)].visited == 0 && GraphIn[(*vi)].gateType == 2 && GraphIn[(*vi)].ReducedCellSet.size() > 0)
                                                GraphIn[(*vi)].cellName = GraphIn[(*vi)].ReducedCellSet[rand() % GraphIn[(*vi)].ReducedCellSet.size()];
                                
                                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_critical, GraphIn); in_vi != in_vi_end ; ++in_vi)
                                        if(GraphIn[(*in_vi)].visited == 0 && GraphIn[(*in_vi)].gateType == 2 && GraphIn[(*in_vi)].ReducedCellSet.size() > 0)
                                                GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].ReducedCellSet[rand() % GraphIn[(*in_vi)].ReducedCellSet.size()];
                        }
                        
                        temp_totalViol = 0.0;
                        for(it_paths = PB.critical_paths.begin(); it_paths != PB.critical_paths.end(); it_paths++)
                        {
                                GraphIn.pathTiming(*it_paths, *(this->LpPtr), *(this->TpPtr), fallSlew, riseSlew,
                                                   fallArrival, riseArrival, totalCapViol, totalSlewViol, totalSlackViol);
                                
                                //temp_totalViol += totalCapViol + totalSlewViol + totalSlackViol;
                                temp_totalViol += totalSlackViol;
                        }
                         
                        if(cur_best_timing > temp_totalViol)
                        {
                                cur_best_timing = temp_totalViol;
                                for(it_critical = critical_gates.begin(); it_critical != critical_gates.end(); it_critical++)
                                {
                                        /*
                                        for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_critical, GraphIn); vi != vi_end ; ++vi)
                                                GraphIn[(*vi)].tempCellName =  GraphIn[(*vi)].cellName;
                                        
                                        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_critical, GraphIn); in_vi != in_vi_end ; ++in_vi)
                                                GraphIn[(*in_vi)].tempCellName =  GraphIn[(*in_vi)].cellName;
                                        */
                                        GraphIn[(*it_critical)].tempCellName =  GraphIn[(*it_critical)].cellName;
                                }
                        }
                }        
        }
        //cout<<"NOT OUT!"<<endl;
        for(it_critical = critical_gates.begin(); it_critical != critical_gates.end(); it_critical++)
        {
                /*
                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_critical, GraphIn); vi != vi_end ; ++vi)
                {
                        GraphIn[(*vi)].visited = 1;
                        GraphIn[(*vi)].cellName = GraphIn[(*vi)].tempCellName;
                }
                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_critical, GraphIn); in_vi != in_vi_end ; ++in_vi)
                {
                        GraphIn[(*in_vi)].visited = 1;
                        GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].tempCellName;
                }
                */
                GraphIn[(*it_critical)].cellName = GraphIn[(*it_critical)].tempCellName;
                GraphIn[(*it_critical)].visited = 1;
        }

        //test for impact of the whole path blossom
        cout<<"For gate "<< in <<endl; 
        vector<vertex_descriptor>::iterator it_node;
        for(it_paths = PB.critical_paths.begin(); it_paths != PB.critical_paths.end(); it_paths++)
        {
                for(it_gate = (*it_paths).begin(); it_gate != (*it_paths).end(); it_gate++)
                {
                        /*
                        cout<<*it_gate<<"\t"<< GraphIn[*it_gate].Slack_Violation <<
                        "\t"<< GraphIn[*it_gate].Slew_Violation << 
                        "\t"<< GraphIn[*it_gate].Cap_Violation<<endl;
                        */
                        it_node = std::find(GraphIn.nodes_under_inspection.begin(), GraphIn.nodes_under_inspection.end(), *it_gate);
                        if(it_node == GraphIn.nodes_under_inspection.end())
                                GraphIn.nodes_under_inspection.push_back(*it_gate);
                        
                        //for(it_node = GraphIn.nodes_under_inspection.begin(); it_node = GraphIn.nodes_under_inspection.begin();)
                }
                //cout<<"Next Path of gate "<<in<<endl;
        }
}


void Cone :: heuristic2(CircuitGraph& GraphIn)
{
        multimap<double, vertex_descriptor> rankMap;
        multimap<double, vertex_descriptor>::reverse_iterator it;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        this->clear_flag(GraphIn);
        for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                if(GraphIn[*vi].Slack_Violation + GraphIn[*vi].Slew_Violation + GraphIn[*vi].Cap_Violation != 0.0)
                        rankMap.insert( pair<double, vertex_descriptor> 
                                        (GraphIn[*vi].Slack_Violation + GraphIn[*vi].Slew_Violation + GraphIn[*vi].Cap_Violation, *vi) );
        
        int i = 0, vn = boost::num_vertices(GraphIn) ;
        for (it = rankMap.rbegin(); it != rankMap.rend(); it++)
        {
                if(i >= 0.01 * vn)
                        break;
                
                //if(GraphIn[it->second].gateType == 2)
                //this->single_gate_fixing(GraphIn, it->second);
                
                i++;
        }
}


void Cone :: heuristic3(CircuitGraph& GraphIn)
{
        int flag;
        vertex_descriptor node;
        set<vertex_descriptor> temp;//get rid of overlap

        vector<NodeSlackStruct>::iterator it;
        set<vertex_descriptor>::iterator it_temp;
        CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        this->clear_flag(GraphIn);
        //int vn = boost::num_vertices(GraphIn) ;
        //for(int i = 0; i < vn; i++)
        for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
        {
                
                if(GraphIn[*vi].gateType != 2)
                        continue;
                
                GraphIn[*vi].level = 0;
                
                node = *vi;
                //while(find_fanout_critical_path(node, GraphIn) == false)
                //GraphIn[*vi].level++;
                //GraphIn[*vi].level++;//make sure leveling is not 0
                
                //cout<<"level is "<<GraphIn[*vi].level<<endl;
                //double temp_total = 0.0;
                //double temp_total = GraphIn[*vi].Slack_Violation;
                //CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
                //for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(*vi, GraphIn); 
                //adj_vi != adj_vi_end ; ++adj_vi)
                //temp_total += GraphIn[*adj_vi].Slack_Violation;
                
                //GraphIn[*vi].lessSharing = temp_total 
                // / (boost::out_degree(*vi,GraphIn) * GraphIn[*vi].level);
                GraphIn[*vi].lessSharing = GraphIn[*vi].Slack_Violation;
                
                //GraphIn[*vi].lessSharing = GraphIn[*vi].Slack_Violation 
                //* (boost::out_degree(*vi,GraphIn) / GraphIn[*vi].level);
                //cout<<"less sharing is " << GraphIn[*vi].lessSharing <<endl;

                NodeSlackStruct myNSS;
                myNSS.vertexDescriptor = *vi;
                myNSS.negativeSlack = GraphIn[*vi].lessSharing;
                GraphIn.nodeSlackVector.push_back(myNSS);
                
        }
        
        //sorting
        std::sort(GraphIn.nodeSlackVector.begin(), GraphIn.nodeSlackVector.end(), sortingFunction());
        // double max_neg_slack = GraphIn.nodeSlackVector[0].negativeSlack;
        // bool state;
        // int count_changed = 0;
        // for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
        // {
        //         if(GraphIn[*vi].gateType != 2 && GraphIn[*vi].Slack_Violation < 0.01)
        //                 continue;
                
        //         double factor = GraphIn[*vi].Slack_Violation / max_neg_slack;
        //         GraphIn.stepSampleGateAngle(*vi, *(this->LpPtr), 4, GraphIn[*vi].ReducedCellSet, 1-factor, 1, state);
        //         //GraphIn.sampleGateAngleGreedy (*vi, *(this->LpPtr), 1, GraphIn[*vi].ReducedCellSet, 1-factor, 1, state);
        //         if(GraphIn[*vi].ReducedCellSet.size() != 0)
        //         {
        //                 GraphIn[*vi].cellName = GraphIn[*vi].ReducedCellSet[0];
        //                 count_changed++;
        //         }
        //         //(*this)[(*it).vertexDescriptor].cellName.assign(this->previousCell((*it).vertexDescriptor)) ;	
        // }
        // cout<<"The # of gates changed " << count_changed <<endl;
        //choosing from the list
        // int i = 0, vn = boost::num_vertices(GraphIn) ;
        //for(it = GraphIn.nodeSlackVector.begin(); it != GraphIn.nodeSlackVector.end(); it++)
        //{
        //if(it->negativeSlack != 0.0)
        //cout<<"violation number is "<<it->negativeSlack<<endl;
        //if(i >= 0.3 * vn)
        //if(i >= 0.01 * vn)
        //break;
        //choose_3_consecutive(GraphIn, it->negativeSlack, it->vertexDescriptor, critical_gates);
                //single_gate_fixing(GraphIn, it->vertexDescriptor, critical_gates);                
                //this->single_gate_fixing(GraphIn, it->vertexDescriptor);
        //i++;
//}
        
        
        //for testing_______________________________________________________________________
        //test to see the optimization results of a single blossum 
        
        // vector<vertex_descriptor> critical_gates;
        // if(GraphIn.nodeSlackVector.size() != 0)
        // {
        //         choose_3_consecutive(GraphIn, GraphIn.nodeSlackVector[0].negativeSlack, GraphIn.nodeSlackVector[0].vertexDescriptor, critical_gates);
        //         single_gate_fixing(GraphIn, GraphIn.nodeSlackVector[0].vertexDescriptor, critical_gates);                
        // }
        //for testing_______________________________________________________________________
        
        
        for(it = GraphIn.nodeSlackVector.begin(); it != GraphIn.nodeSlackVector.end(); it++)
        {
                
                flag = 0;
                myStack.push(it->vertexDescriptor);
                GraphIn[it->vertexDescriptor].visited = 1;
                
                while(!myStack.empty())
                {
                        if(DFS(myStack.top(), temp, myStack, GraphIn) == true)
                                myStack.pop();
                        else
                        {
                                flag = 1;
                                break;
                        }
                }
                
                if(flag == 1)//DFS returns false
                {
                        while (!myStack.empty())
                                myStack.pop();
                        
                }
                else
                {
                        
                        //if(GraphIn[it->vertexDescriptor].gateType == 2)
                        //this->single_gate_fixing(GraphIn, it->vertexDescriptor);
                        
                        for(it_temp = temp.begin(); it_temp != temp.end(); it_temp++)
                                GraphIn[*it_temp].fixed = 1;
                        
                }
                
                //temp won't contain root node
                temp.clear();
                assert(myStack.empty());
        }
}


void Cone :: heuristic4(CircuitGraph& GraphIn)
{
        int flag, cone_id;
        vertex_descriptor node;
        set<vertex_descriptor> temp;//get rid of overlap

        vector<vertex_descriptor> critical_gates;
        vector<NodeSlackStruct>::iterator it;
        set<vertex_descriptor>::iterator it_temp;
        CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        this->clear_flag(GraphIn);
        //this->update_DFF_timing(GraphIn);
        //this->normal_cone_sorting();
        int count = 0;
        for(cone_id = 0; cone_id < this->cones.size(); cone_id++)
        {
                
                if(this->cones[cone_id].done == 1)
                        continue;
                
                if(this->cones[cone_id].gate_ids.size() == 0)
                        continue;
                
                if(this->cones[cone_id].total_timing_viol < 0.00001)
                        continue;
                
                critical_gates.clear();
                vertex_descriptor v = this->cones[cone_id].gate_idx;
                while(this->extract_critical_path(v, cone_id, GraphIn) == false);
                this->clear_flag(GraphIn);

                if(critical_gates_per_path(GraphIn, this->cones[cone_id].critical_path, critical_gates) == false)
                        continue;
                
                cout<<"optimizing cone " << cone_id << endl;
                if(critical_gates.size() > 0)
                {
                        single_gate_fixing(GraphIn, critical_gates[0], critical_gates);
                        break;
                }
                
                count++;
        }
        
        cout<< "Number of cones optimized in this round is "<< count<<endl;
}


void Cone :: find_critical_gates_Hybcone(CircuitGraph& GraphIn, const int big_cone_id, const int coarse)
{

        int flag = 0;
        double temp_violation;
        int count_gates_in_BC = 0;
        
        std::vector<int>::iterator it_int;
        std::vector<vertex_descriptor>::iterator it;
        std::vector<vertex_descriptor>::iterator it1;
        std::multimap<double, vertex_descriptor> RankMap;//use a map for rank
        std::multimap<double, vertex_descriptor>::iterator it_RM;
        
        this->big_cones[big_cone_id].critical_gates.clear();
        //rank all nodes in the big cone first
        for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
        {
                for(it = this->cones[*it_int].critical_path.begin(); it != this->cones[*it_int].critical_path.end(); it++)
                {
                        if(GraphIn[*it].visited == 0)
                                flag = 1;
                        
                        if(this->big_cones[big_cone_id].cone_ids.size() > 1)
                        {
                                for(it1 = this->big_cones[big_cone_id].common_gates.begin(); it1 != this->big_cones[big_cone_id].common_gates.end(); it1++)
                                        if(*it != *it1)
                                        {
                                                temp_violation = GraphIn[(*it)].Slew_Violation + GraphIn[(*it)].Slack_Violation;
                                                RankMap.insert(std::pair<double,vertex_descriptor>(temp_violation,*it));
                                        }
                        }
                        else
                        {
                                temp_violation = GraphIn[(*it)].Slew_Violation + GraphIn[(*it)].Slack_Violation;
                                RankMap.insert(std::pair<double,vertex_descriptor>(temp_violation,*it));
                        }
                }
                
                count_gates_in_BC += this->cones[*it_int].critical_path.size();
        }
        
        //if(flag == 0)
        //this->big_cones[big_cone_id].done = 1;
        
        for(it = this->big_cones[big_cone_id].common_gates.begin(); it != this->big_cones[big_cone_id].common_gates.end(); it++)
        {
                if(this->big_cones[big_cone_id].cone_ids.size() > 1)
                {
                        temp_violation = GraphIn[(*it)].Slew_Violation + GraphIn[(*it)].Slack_Violation;
                        RankMap.insert(std::pair<double,vertex_descriptor>(temp_violation,*it));
                }
        }
        
        this->big_cones[big_cone_id].most_violation = RankMap.rbegin()->first;
        /*
        cout<<"Most Violation in cone is "<< this->big_cones[big_cone_id].most_violation <<endl;
        cout<<"Big Cone id "<< big_cone_id << " has common gates: " << endl;
        for(it1 = this->big_cones[big_cone_id].common_gates.begin(); it1 != this->big_cones[big_cone_id].common_gates.end(); it1++)
                cout<<*it1<<"\t";
        cout<<endl;
        
        for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
        {
                cout<<"normal cone id "<< *it_int << " has critical path:" <<endl;
                for(it1 = this->cones[*it_int].critical_path.begin(); it1 != this->cones[*it_int].critical_path.end(); it1++)
                        cout<<*it1<<"\t";
                cout<<endl;
        }

        cout<<"Normal cone number is "<<this->big_cones[big_cone_id].cone_ids.size() <<endl;
        cout<<"Number of common gates is "<< this->big_cones[big_cone_id].common_gates.size() <<endl;
        cout<<"First, Number of gates in critical paths of cone "<< big_cone_id << " is " << count_gates_in_BC <<endl;
        count_gates_in_BC -= (this->big_cones[big_cone_id].cone_ids.size() - 1) * this->big_cones[big_cone_id].common_gates.size();
        cout<<"Second, Number of gates in critical paths of cone "<< big_cone_id << " is " << count_gates_in_BC <<endl;
        */
        //in this case we don't care about the node has been visited or not
        if(count_gates_in_BC <= this->Fixed_Gates_Per_Itr)
        {
                for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
                {
                        for(it = this->cones[*it_int].critical_path.begin(); it != this->cones[*it_int].critical_path.end(); it++)
                        {
                                GraphIn[*it].visited = 1;
                                this->big_cones[big_cone_id].critical_gates.push_back(*it);
                        }
                }
                
                std::unique(this->big_cones[big_cone_id].critical_gates.begin(), this->big_cones[big_cone_id].critical_gates.end(), same_vertex);
                return;
        }
        
        //int pick_num = (!coarse)?  this->Fixed_Gates_Per_Itr : 
        //(count_gates_in_BC > 16)? 8 :(0.5 * count_gates_in_BC) ;
        int start_pick_num = 3;
        //int pick_num = (!coarse)?  this->Fixed_Gates_Per_Itr : (count_gates_in_BC > 16)? 3 : 3;
        int pick_num = start_pick_num - coarse;
        //int pick_num = 2;

        //cout<<"current critical gates' size is "<<this->big_cones[big_cone_id].critical_gates.size()<<endl;
        //cout<<"pick num is "<< pick_num <<endl;
        
        //choose the one that is not visted but also in the common gates first
        for(it = this->big_cones[big_cone_id].common_gates.begin(); it != this->big_cones[big_cone_id].common_gates.end(); it++)
        {
                if(GraphIn[*it].visited == 0)
                {
                        GraphIn[*it].visited = 1;
                        this->big_cones[big_cone_id].critical_gates.push_back(*it);
                }
                
                if(this->big_cones[big_cone_id].critical_gates.size() == pick_num)
                        return;
        }
        
        //pick from the rest in the ranked order, only not visted nodes
        for(it_RM = RankMap.begin(); it_RM != RankMap.end(); it_RM++)
        {
                if(GraphIn[it_RM->second].visited == 1)
                        continue;
                
                GraphIn[it_RM->second].visited = 1;
                this->big_cones[big_cone_id].critical_gates.push_back(it_RM->second);
                
                if(this->big_cones[big_cone_id].critical_gates.size() == pick_num)
                        return;
        }
        
        //if still not meet the pick_num, choose the ones that are top on the list
        for(it_RM = RankMap.begin(); it_RM != RankMap.end(); it_RM++)
        {                
                it = std::find(this->big_cones[big_cone_id].critical_gates.begin(), this->big_cones[big_cone_id].critical_gates.end(), it_RM->second);
                
                if(it == this->big_cones[big_cone_id].critical_gates.end())
                        this->big_cones[big_cone_id].critical_gates.push_back(it_RM->second);
                
                if(this->big_cones[big_cone_id].critical_gates.size() == pick_num)
                        return;
        }
}        


bool less_total_violation(node_rank NR1, node_rank NR2)
{
        return (NR1.total_violation < NR2.total_violation);
}


bool more_feasible_time(node_rank NR1, node_rank NR2)
{
        return (NR1.feasible_time > NR2.feasible_time);
}


bool Cone :: sample_procedure(CircuitGraph& GraphIn, const int big_cone_id, const int NSamples, const int coarse)
{
        
        int i, flag;
        int cell_combination, temp_cell_combination;
        int temp_gate_size, critical_gate_sample_size = 0;
        int sample_times = (coarse)? 10 : this->Sample_Times;
        
        double totalCapViol, totalSlewViol, totalSlackViol, cur_best_timing = 1.0e20;
        double fallSlew, riseSlew, temp_totalViol, best_totalViol;
        double fallArrival, riseArrival, temp_total_leakage, best_total_leakage;

        LibParserCellInfo *LPCI;
        CircuitGraph::adjacency_iterator vi, vi_end ;
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;

        vertex_descriptor temp_vi;
        vector<node_rank> myRank;
        std::vector<int>::iterator it_int;
        std::vector<vertex_descriptor>::iterator it, it_path;

        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                GraphIn[*it].visited = 0;
        
        //reduced sample set for gates in critical paths and their neighbourhoods
        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
        {
                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it, GraphIn); vi != vi_end ; ++vi)
                {
                        temp_vi = *vi;
                        if(GraphIn[temp_vi].gateType == 2)
                                this->find_samples_per_gate(GraphIn, temp_vi, big_cone_id, NSamples, false, coarse);
                }
                
                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it, GraphIn); in_vi != in_vi_end ; ++in_vi)
                {
                        temp_vi = *in_vi;
                        if(GraphIn[temp_vi].gateType == 2)
                                this->find_samples_per_gate(GraphIn, temp_vi, big_cone_id, NSamples, false, coarse);
                }
                
                if(GraphIn[*it].gateType == 2)
                {
                        GraphIn[*it].visited = 1;
                        temp_gate_size = this->find_samples_per_gate(GraphIn, *it, big_cone_id, NSamples, true, coarse);
                }       

                if(temp_gate_size > critical_gate_sample_size)
                        critical_gate_sample_size = temp_gate_size;
        }
        
        // for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
        // {
        //         for(it_path = this->cones[*it_int].critical_path.begin(); it_path != this->cones[*it_int].critical_path.end(); it_path++)
        //         {
        //                 it = std::find(this->big_cones[big_cone_id].critical_gates.begin(), this->big_cones[big_cone_id].critical_gates.end(), *it_path);
        //                 if(it == this->big_cones[big_cone_id].critical_gates.end())
        //                 {
        //                         for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_path, GraphIn); vi != vi_end ; ++vi)
        //                         {
        //                                 temp_vi = *vi;
        //                                 if(GraphIn[temp_vi].gateType == 2)
        //                                         this->find_samples_per_gate(GraphIn, temp_vi, big_cone_id, NSamples, false, coarse);
        //                         }
                                
        //                         for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_path, GraphIn); in_vi != in_vi_end ; ++in_vi)
        //                         {
        //                                 temp_vi = *in_vi;
        //                                 if(GraphIn[temp_vi].gateType == 2)
        //                                         this->find_samples_per_gate(GraphIn, temp_vi, big_cone_id, NSamples, false, coarse);
        //                         }
                                
        //                         if(GraphIn[*it_path].gateType == 2)
        //                                 this->find_samples_per_gate(GraphIn, *it_path, big_cone_id, NSamples, false, coarse);
        //                 }
        //         }
        // }
        
        //real sample procedure begins, note critical gate size can be larger than reduced set size
        for(cell_combination = 0; cell_combination < pow(critical_gate_sample_size, this->big_cones[big_cone_id].critical_gates.size()); cell_combination++)
        {
                
                flag = 0;
                node_rank* myNR = new node_rank;
                temp_cell_combination = cell_combination;
                best_totalViol = 100000000.0;
                best_total_leakage = 100000000.0;
                
                for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                {
                        if(GraphIn[(*it)].ReducedCellSet.size() != 0)
                        {
                                if(temp_cell_combination % critical_gate_sample_size >= GraphIn[(*it)].ReducedCellSet.size())
                                {
                                        flag = 1;
                                        break;
                                }

                                if(GraphIn[(*it)].gateType == 2 && GraphIn[(*it)].ReducedCellSet.size() != 1)
                                        GraphIn[(*it)].cellName = GraphIn[(*it)].ReducedCellSet[temp_cell_combination % critical_gate_sample_size];
                                
                                temp_cell_combination /= critical_gate_sample_size;
                        }
                }
                
                if(flag == 1)
                        continue;

                for(i = 0; i < sample_times; i++)
                {
                        srand ( time(NULL) );
                        
                        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                        {
                                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it, GraphIn); vi != vi_end ; ++vi)
                                        if(GraphIn[(*vi)].visited == 0 && GraphIn[(*vi)].gateType == 2 && GraphIn[(*vi)].ReducedCellSet.size() > 0)
                                                GraphIn[(*vi)].cellName = GraphIn[(*vi)].ReducedCellSet[rand() % GraphIn[(*vi)].ReducedCellSet.size()];
                                
                                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it, GraphIn); in_vi != in_vi_end ; ++in_vi)
                                        if(GraphIn[(*in_vi)].visited == 0 && GraphIn[(*in_vi)].gateType == 2 && GraphIn[(*in_vi)].ReducedCellSet.size() > 0)
                                                GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].ReducedCellSet[rand() % GraphIn[(*in_vi)].ReducedCellSet.size()];
                        }
                        
                        // for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
                        // {
                        //         for(it_path = this->cones[*it_int].critical_path.begin(); it_path != this->cones[*it_int].critical_path.end(); it_path++)
                        //         {
                                        
                        //                 it = std::find(this->big_cones[big_cone_id].critical_gates.begin(), this->big_cones[big_cone_id].critical_gates.end(), *it_path);
                                        
                        //                 if(it == this->big_cones[big_cone_id].critical_gates.end())
                        //                 {
                                                
                        //                         for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_path, GraphIn); vi != vi_end ; ++vi)
                        //                                 if(GraphIn[(*vi)].visited == 0 && GraphIn[(*vi)].gateType == 2 && GraphIn[(*vi)].ReducedCellSet.size() > 0)
                        //                                         GraphIn[(*vi)].cellName = GraphIn[(*vi)].ReducedCellSet[rand() % GraphIn[(*vi)].ReducedCellSet.size()];
                                
                        //                         for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_path, GraphIn); in_vi != in_vi_end ; ++in_vi)
                        //                                 if(GraphIn[(*in_vi)].visited == 0 && GraphIn[(*in_vi)].gateType == 2 && GraphIn[(*in_vi)].ReducedCellSet.size() > 0)
                        //                                         GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].ReducedCellSet[rand() % GraphIn[(*in_vi)].ReducedCellSet.size()];

                        //                         if(GraphIn[(*it_path)].visited == 0 && GraphIn[(*it_path)].gateType == 2 && GraphIn[(*it_path)].ReducedCellSet.size() > 0)
                        //                                 GraphIn[(*it_path)].cellName = GraphIn[(*it_path)].ReducedCellSet[rand() % GraphIn[(*it_path)].ReducedCellSet.size()];
                        //                 }
                        //         }
                        // }
                        
                        temp_totalViol = 0.0;
                        for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
                        {
                                /*
                                cout<<"normal cone id is "<<*it_int<<endl;
                                for(it_path = this->cones[*it_int].critical_path.begin(); it_path != this->cones[*it_int].critical_path.end(); it_path++)
                                        cout<<*it_path<<"\t"<<GraphIn[*it_path].cellName<<"\t"<<GraphIn[*it_path].instanceName<<"\t";
                                cout<<endl;
                                */
                                GraphIn.pathTiming(this->cones[*it_int].critical_path, 
                                                   *(this->LpPtr), *(this->TpPtr), fallSlew, riseSlew,
                                                   fallArrival, riseArrival, totalCapViol, totalSlewViol, totalSlackViol);
                                
                                //temp_totalViol += totalCapViol +
                                //totalSlewViol + totalSlackViol;
                                temp_totalViol += totalSlackViol;
                        }
                        
                        if(cur_best_timing > temp_totalViol)
                        {
                                cur_best_timing = temp_totalViol;
                                for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                                {
                                        //for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it, GraphIn); vi != vi_end ; ++vi)
                                        //GraphIn[(*vi)].tempCellName =  GraphIn[(*vi)].cellName;
                                        
                                        //for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it, GraphIn); in_vi != in_vi_end ; ++in_vi)
                                        //GraphIn[(*in_vi)].tempCellName =  GraphIn[(*in_vi)].cellName;
                                        
                                        GraphIn[(*it)].tempCellName =  GraphIn[(*it)].cellName;
                                }
                        }
                        // if(temp_totalViol == 0.0)
                        // {
                        //         flag++;
                        //         temp_total_leakage = 0.0;
                                
                        //         for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
                        //         {
                        //                 for(it_path = this->cones[*it_int].critical_path.begin();it_path != this->cones[*it_int].critical_path.end(); it_path++)
                        //                 {
                        //                         LPCI = &(this->LpPtr->mapStandardLibraryCells[ GraphIn[ *it_path ].cellName ]);
                        //                         temp_total_leakage += LPCI->leakagePower; 
                        //                 }
                        //         }
                                
                        //         for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                        //         {
                        //                 LPCI = &(this->LpPtr->mapStandardLibraryCells[ GraphIn[ *it ].cellName ]);
                        //                 temp_total_leakage -= (this->big_cones[big_cone_id].cone_ids.size() - 1) * LPCI->leakagePower;
                        //         }
                                
                        //         if(temp_total_leakage < best_total_leakage)
                        //                 best_total_leakage = temp_total_leakage;
                        // }
                        // else
                        // {
                        //         if(flag == 0)
                        //                 if(best_totalViol > temp_totalViol)
                        //                         best_totalViol = temp_totalViol;
                        // }
                        
                }                
                
                // if(flag == 0)
                // {
                //         myNR->feasible_time = 0;
                //         myNR->cell_combination = cell_combination;
                //         myNR->total_violation = best_totalViol;
                //         myNR->total_leakage = 0.0;
                // }
                // else
                // {
                //         myNR->feasible_time = flag;
                //         myNR->cell_combination = cell_combination;
                //         myNR->total_violation = 0.0;
                //         myNR->total_leakage = best_total_leakage;
                // }
                
                // myRank.push_back(*myNR);
        }
        
        /*
        //sort by feasible time first, then total violation, at last judge by leakage
        std::sort(myRank.begin(),myRank.end(),more_feasible_time);

        if(myRank.size() > 0 && myRank[0].feasible_time == 0)
        {
                std::vector<node_rank>::iterator it_nr;
                std::sort(myRank.begin(),myRank.end(),less_total_violation);
                
                if(myRank[0].total_violation != 0.0)
                {
                        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                        {
                                if(critical_gate_sample_size > 0 && GraphIn[(*it)].ReducedCellSet.size() > 1)
                                {
                                        GraphIn[(*it)].cellName = GraphIn[(*it)].ReducedCellSet[myRank[0].cell_combination % critical_gate_sample_size];
                                        myRank[0].cell_combination /= critical_gate_sample_size;
                                }
                        }
                }
                else
                {
                        int best_cell_combination;
                        double temp_total_leakage = 1000000.0;
                        for(it_nr = myRank.begin(); it_nr != myRank.end(); it_nr++)
                        {
                                if(it_nr->total_violation != 0.0)
                                        break;
                        
                                if(it_nr->total_leakage < temp_total_leakage)
                                {
                                        temp_total_leakage = it_nr->total_leakage;
                                        best_cell_combination = it_nr->cell_combination;
                                }     
                        }
                        
                        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                        {
                                if(critical_gate_sample_size != 0 && GraphIn[(*it)].ReducedCellSet.size() > 1)
                                {
                                        GraphIn[(*it)].cellName = GraphIn[(*it)].ReducedCellSet[best_cell_combination % critical_gate_sample_size];
                                        best_cell_combination /= critical_gate_sample_size;
                                }
                        }
                }
        }

        cout<<"Sampling for critical path finished....."<<endl;
        
        //set all neighbouring nodes to minimum leakage
        for(it_int = this->big_cones[big_cone_id].cone_ids.begin(); it_int != this->big_cones[big_cone_id].cone_ids.end(); it_int++)
        {
                for(it_path = this->cones[*it_int].critical_path.begin();it_path != this->cones[*it_int].critical_path.end(); it_path++)
                {
                        if(GraphIn[(*it_path)].gateType == 2 && GraphIn[(*it_path)].visited == 0)
                                GraphIn[(*it_path)].cellName = GraphIn[(*it_path)].listOfCells[0];
                        
                        for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it_path, GraphIn); vi != vi_end ; ++vi)
                                if(GraphIn[(*vi)].visited == 0 && GraphIn[(*vi)].gateType == 2)
                                        GraphIn[(*vi)].cellName = GraphIn[(*vi)].listOfCells[0];
                        
                        for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it_path, GraphIn); in_vi != in_vi_end ; ++in_vi)
                                if(GraphIn[(*in_vi)].visited == 0 && GraphIn[(*in_vi)].gateType == 2)
                                        GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].listOfCells[0];
                }       
        }
        
        if(myRank.size() > 0 && myRank[0].total_violation != 0.0)
                return false;
        */

        for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
        {
                /*
                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*it, GraphIn); vi != vi_end ; ++vi)
                {
                        GraphIn[(*vi)].visited = 1;
                        GraphIn[(*vi)].cellName = GraphIn[(*vi)].tempCellName;
                }
                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*it, GraphIn); in_vi != in_vi_end ; ++in_vi)
                {
                        GraphIn[(*in_vi)].visited = 1;
                        GraphIn[(*in_vi)].cellName = GraphIn[(*in_vi)].tempCellName;
                }
                */
                GraphIn[(*it)].cellName = GraphIn[(*it)].tempCellName;
                GraphIn[(*it)].visited = 1;
        }
        
        return true;
}


bool more_overlap(big_cone BC1, big_cone BC2)
{
        return (BC1.cone_ids.size() > BC2.cone_ids.size());
}


bool Cone :: sampling(CircuitGraph& GraphIn, int coarse)
{
        int big_cone_id;
        int cone_sample_size = (this->big_cones.size() > 100)? 100 : this->big_cones.size();
        //int cone_sample_size = 1;
        double alpha = 0.8;
        
        bool state = true;
        vector<vertex_descriptor>::iterator it;
        CircuitGraph::adjacency_iterator vi, vi_end ;
        CircuitGraph::inv_adjacency_iterator in_vi, in_vi_end ;
        
        //these are all for testing
        /*
        boost::graph_traits<CircuitGraph>::vertex_iterator node_vi, node_vi_end ;
        for (boost::tie(node_vi, node_vi_end) = boost::vertices(GraphIn) ; node_vi != node_vi_end ; ++node_vi)
        {
                cout<<"Vertex "<< *node_vi << " has fan in nodes " << endl;
                for (boost::tie(in_vi, in_vi_end) = boost::inv_adjacent_vertices(*node_vi, GraphIn); in_vi != in_vi_end ; ++in_vi)
                        cout<<*in_vi<<"\t"<<GraphIn[*in_vi].instanceName<<"\t"<<GraphIn[*in_vi].cellName<<endl;

                cout<<"has fan out nodes "<<endl;
                
                for (boost::tie(vi, vi_end) = boost::adjacent_vertices(*node_vi, GraphIn); vi != vi_end ; ++vi)
                        cout<<*vi<<"\t"<<GraphIn[*vi].instanceName<<"\t"<<GraphIn[*vi].cellName<<endl;
        }

        int vn = boost::num_vertices(GraphIn);
        for(int i = 0; i < vn; i++)
        {
                cout<<"Vertex "<< i <<":\t";
                cout<<"Slack Violation is "<< GraphIn[i].Slack_Violation << "\t";
                cout<<"Slew Violation is "<< GraphIn[i].Slew_Violation << "\t";
                cout<<"Cap Violation is "<< GraphIn[i].Cap_Violation << endl;
        }
        
        for(int i = 0; i < vn; i++)
                cout<<"node id "<< i << "Instance Name" << GraphIn[i].instanceName << " Cell Name "<<GraphIn[i].cellName
                    << " FootPrint "<< GraphIn[i].footPrint <<endl;
        */
        
        //Change this part for multithreading
        int finish_first_round = 0;
        //big_cone_id = 0;
        for(big_cone_id = 0; big_cone_id < cone_sample_size * alpha; big_cone_id++)
        {
        
                if(this->big_cones[big_cone_id].cone_ids.size() == 0 || 
                   (this->big_cones[big_cone_id].cone_ids.size() == 1 && 
                    this->cones[ this->big_cones[big_cone_id].cone_ids[0] ].critical_path.size() ==0))
                        continue;
                
                //since we sort in the decreasing order before sampling is called
                if(this->big_cones[big_cone_id].total_timing_viol == 0.0)
                        break;
                
                cout<<"Optimizing Hybrid Cone "<< big_cone_id <<endl;
                
                this->find_critical_gates_Hybcone(GraphIn, big_cone_id, coarse);
                /*
                cout<<"Critical gates are "<<endl;
                for(it = this->big_cones[big_cone_id].critical_gates.begin(); it != this->big_cones[big_cone_id].critical_gates.end(); it++)
                        cout<< *it << "\t";
                cout<<endl;
                */
                int step_size = 2; int NSamples = this->ReducedCellSize;
                
                if(this->big_cones[big_cone_id].done == 0)
                {
                        finish_first_round = 1;
                        this->sample_procedure(GraphIn, big_cone_id, NSamples, coarse);
                }
                else
                {
                        continue;
                        /*
                        coarse = false;
                        this->find_critical_gates_Hybcone(GraphIn, big_cone_id, coarse);
                        while(this->sample_procedure(GraphIn, big_cone_id, NSamples, coarse) == false)
                        {      
                                NSamples += step_size;
                                if(NSamples > 10)
                                        break;
                        }
                        */
                }
        }
        //end of threading
        
        // int NUM_THREADS = 4 ;
	
        // MyThread threads[NUM_THREADS] ;
        // _threadArgument thr_data[NUM_THREADS] ;
	
        // int cones_per_thread = cone_sample_size / NUM_THREADS ;

        // /* create threads */
        // for (int i = 0; i < NUM_THREADS; ++i) {
	
			
        //         thr_data[i].start = i * cones_per_thread;
        //         thr_data[i].end = (i != NUM_THREADS - 1) ?  (i+1) * cones_per_thread : cone_sample_size ;
        //         thr_data[i].coarse = coarse ;
        //         thr_data[i].graphPtr = &GraphIn ;
        //         thr_data[i].conePtr =  this ;
			
        //         //threads[i] = MyThread() ;
        //         threads[i].start(&thr_data[i]) ;
        // }
		
		
        // for (int i = 0; i < NUM_THREADS; ++i) {
        //         threads[i].join() ;
        // }

        if(finish_first_round == 0)
        {
                for(big_cone_id = 0; big_cone_id < this->big_cones.size(); big_cone_id++)
                        this->big_cones[big_cone_id].done = 0;
                
                this->clear_flag(GraphIn);
                cout<<"We are done for the first round!"<<endl;
                return true;
        }
        
        return false;
}


bool Cone :: update_DFF_timing(CircuitGraph& GraphIn)
{
        for(int cone_id = 0; cone_id != this->cones.size(); cone_id++)
        {
                string temp_name = GraphIn[this->cones[cone_id].gate_idx].instanceName 
                        + "/" + "d";
                double temp = 0.0;
                if(this->TpPtr->PinsTiming[temp_name].riseSlack < 0)
                        temp += abs(this->TpPtr->PinsTiming[temp_name].riseSlack);
                
                if(this->TpPtr->PinsTiming[temp_name].fallSlack < 0)
                        temp += abs(this->TpPtr->PinsTiming[temp_name].fallSlack);
                
                if(this->TpPtr->PinsTiming[temp_name].riseTransition > 300)
                        temp += 300 - abs(this->TpPtr->PinsTiming[temp_name].riseTransition);
                
                if(this->TpPtr->PinsTiming[temp_name].fallTransition > 300)
                        temp += 300 - abs(this->TpPtr->PinsTiming[temp_name].fallTransition);
                
                this->cones[cone_id].total_timing_viol = temp;
                
                if(temp = 0.0)
                {
                        cout<<"Cone "<< cone_id <<" is done!!!"<<endl;
                        this->cones[cone_id].done = 1;        
                        return true;
                }
                else
                {
                        if(this->cones[cone_id].done == 1)
                        {
                                this->cones[cone_id].done = 0;
                                cout<<"Cone "<< cone_id << " initially is done, now become invalid!"<<endl;
                        }
                }
        }
        
        return false;
}


template <class T>
class more_total_viol
{
public:
        bool operator()(const T a, const T b){
               return (a.total_timing_viol > b.total_timing_viol);
        }
};


void Cone :: normal_cone_sorting()
{
        std::sort(this->cones.begin(), this->cones.end(), more_total_viol<cone>());
        /*
        vector<cone>::iterator it;
        cout<<"After normal cone ranking....."<<endl;
        for(it = this->cones.begin(); it != this->cones.end(); it++)
        cout<<it->total_timing_viol<<endl;
        */
}


void Cone :: hybrid_cone_sorting()
{
        std::sort(this->big_cones.begin(), this->big_cones.end(), more_total_viol<big_cone>());
        /*
        vector<big_cone>::iterator it;
        cout<<"After normal cone ranking....."<<endl;
        for(it = this->big_cones.begin(); it != this->big_cones.end(); it++)
        cout<<it->total_timing_viol<<endl;
        */
}


void Cone :: heuristic_sizing(CircuitGraph& GraphIn)
{
        int flag;
        set<vertex_descriptor> temp;
        vertex_descriptor node;
        vector<NodeSlackStruct>::iterator it;
        set<vertex_descriptor>::iterator it_temp;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        this->clear_flag(GraphIn);
        GraphIn.fillCellSizes();
        //int vn = boost::num_vertices(GraphIn) ;
        //for(int i = 0; i < vn; i++)
        for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
        {
                
                if(GraphIn[*vi].gateType != 2)
                        continue;
                
                GraphIn[*vi].level = 0;
                
                node = *vi;
                while(find_fanout_critical_path(node, GraphIn) == false)
                        GraphIn[*vi].level++;
                GraphIn[*vi].level++;//make sure leveling is not 0
                
                double temp_total = 0.0;
                //double temp_total = GraphIn[*vi].Slack_Violation;
                CircuitGraph::adjacency_iterator adj_vi, adj_vi_end;
                for (boost::tie(adj_vi, adj_vi_end) = boost::adjacent_vertices(*vi, GraphIn); 
                     adj_vi != adj_vi_end ; ++adj_vi)
                        temp_total += GraphIn[*adj_vi].Slack_Violation;
                
                GraphIn[*vi].lessSharing = temp_total 
                        / (boost::out_degree(*vi,GraphIn) * GraphIn[*vi].level);
                
                NodeSlackStruct myNSS;
                myNSS.vertexDescriptor = *vi;
                myNSS.negativeSlack = GraphIn[*vi].lessSharing;
                GraphIn.nodeSlackVector.push_back(myNSS);
                
        }
        
        //sorting
        std::sort(GraphIn.nodeSlackVector.begin(), GraphIn.nodeSlackVector.end(), sortingFunction());
        
        //choosing from the list
        stack<vertex_descriptor> myStack;
        for(it = GraphIn.nodeSlackVector.begin(); it != GraphIn.nodeSlackVector.end(); it++)
        {
                
                flag = 0;
                myStack.push(it->vertexDescriptor);
                GraphIn[it->vertexDescriptor].visited = 1;
                
                while(!myStack.empty())
                        if(DFS(myStack.top(), temp, myStack, GraphIn) == true)
                                myStack.pop();
                        else
                        {
                                flag = 1;
                                break;
                        }
                
                if(flag == 1)
                {
                        while (!myStack.empty())
                                myStack.pop();
                        temp.clear();
                }
                else
                {
                        
                        if(GraphIn[it->vertexDescriptor].gateType == 2)
                        {
                                cout<<"Here Here!"<<endl;
                                GraphIn[it->vertexDescriptor].cellName 
                                        = GraphIn.nextCell(it->vertexDescriptor);
                        }
                        for(it_temp = temp.begin(); it_temp != temp.end(); it_temp++)
                                GraphIn[*it_temp].visited = 1;
                        
                        temp.clear();
                }
                
        }
}


void Cone :: finer_tuning(CircuitGraph& GraphIn)
{
        GraphIn.fillCellSizes();
        vector<string>::iterator it;
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        
        if(GraphIn.mode == 0 || GraphIn.mode == 1)
        {
                for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                {
                        if(GraphIn[*vi].gateType == 2 && GraphIn[*vi].Cap_Violation != 0)
                        {
                                GraphIn[*vi].cellName 
                                        = GraphIn.nextCell(*vi);
                        }
                }
        }
        else if(GraphIn.mode == 2)
        {
                for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                {
                        if(GraphIn[*vi].gateType == 2 && GraphIn[*vi].Slew_Violation != 0)
                        {
                                GraphIn[*vi].cellName 
                                        = GraphIn.nextCell(*vi);
                        }
                }
        }
        else if(GraphIn.mode == 3)
        {
                for (boost::tie(vi, vi_end) = boost::vertices(GraphIn) ; vi != vi_end ; ++vi)
                {
                        if(GraphIn[*vi].gateType == 2 && GraphIn[*vi].Slack_Violation != 0)
                        {
                                GraphIn[*vi].cellName 
                                        = GraphIn.nextCell(*vi);
                        }
                }
        }
}
